/**
 * @auther harfe
 * @date 2021/11/22 21:48
 */

/**
 *给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 */
public class MaxRectange {
    public static void main(String[] args) {
        int[] heights = new int[]{2,1,5,6,2,3};
        MaxRectange maxRectange = new MaxRectange();
        int ans = maxRectange.largestRectangleArea(heights);
        System.out.println(ans);
    }
    /*
    双指针
     */
    public int largestRectangleArea(int[] heights) {

        int len = heights.length;
        //i为头指针，j为尾指针
        int i = 0,j = len - 1;
        int maxArea = 0;
        int area = 0;
        int minnum = 0;

        while (len > 0) {
            for (int k = i; k < j; k++) {
                minnum = heights[k];
                minnum = Math.min(minnum,heights[k]);
            }
            area = (j - i) * minnum;
            maxArea = Math.max(area,maxArea);
            if (heights[i] < heights[j]){
                i++;
            }
            if (heights[j] < heights[i]){
                j--;
            }
        }
        return maxArea;
    }
}
